package com.code.test.ali;

import java.util.Arrays;

/**
 * 差分数组解释：https://labuladong.github.io/zgnb/5/29/
 */

public class Chafen {

    public static void main(String[] args) {

        int[] nums = {0, 2, 5, 4, 9, 7, 10, 0};
        int[] chafen = build(nums);
        System.out.println(Arrays.toString(chafen));

        int[] origin = restore(chafen);
        System.out.println(Arrays.toString(origin));
    }

    public static int[] build(int[] nums) {

        /**
         * nums[i] = nums[i-1]+ diff[i]
         * diff[i-1] 代表 i元素与 （i-1）元素差多少，所以为差分
         */
        int[] chafen = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            chafen[i] = nums[i] - nums[i - 1];
        }
        return chafen;
    }

    public static int[] restore(int[] diff) {
        int[] origin = new int[diff.length];
        origin[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            origin[i] = diff[i] + origin[i-1];
        }
        return origin;
    }
}
